package ljl.alg.hot100;

public class _70_climb_stairs {
    
    /*
     * 别鸡巴混了！
     * */
    public int climbStairs3(int n) {
        int a = 1, b = 1;
        while (n-- > 0) {
            int t = a;
            a = b;
            b = a + t;
        }
        return a;
    }
    
    /*
    * 下面这个矩阵乘法，我看了一个多小时，草他妈！
    * */
    
    /*
     * 快速幂，也不难，写写
     * 1 1     fn     fn + fn-1   fn+1
     * 1 0  *  fn-1 = fn        = fn
     *
     * 1 1   1 1   2 1  1 1   3 2  1 1   5 3
     * 1 0 * 1 0 = 1 1  1 0 = 2 1  1 0 = 3 2
     * 乘一次，第一个元素就是下一个值
     * 乘很多次，可以用矩阵乘法，很简单
     *
     * 感觉不用乘这个 2*1 的矩阵，直接拿原始矩阵就行了
     *
     * 果然，想了一下，确实是不会做的
     * */
    
    /**
     * 写这个题我受尽了委屈，呜呜。。
     */
    int[][] mul2(int[][] a, int[][] b) {
        int[][] res = new int[a.length][b[0].length];
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < b[0].length; j++) {
                for (int k = 0; k < b.length; k++) {
                    res[i][j] += a[i][k] * b[k][j];
                }
            }
        }
        return res;
    }
    
    int[][] fastPower2(int[][] a, int[][] b, int n) {
        int[][] res = b;
        while (n > 0) {
            if ((n & 1) == 1) {
                res = mul2(res, b);
            }
            b = mul2(b, b);
            n >>= 1;
        }
        return mul2(res, a);
    }
    
    public int climbStairs2(int n) {
        return fastPower2(new int[][]{{0}, {1}}, new int[][]{{1, 1}, {1, 0}}, n)[0][0];
    }
    
    /**
     * 经过优化，性能没任何变化
     * 所以不要随便优化
     * <p>
     * 但是简洁了很多
     */
    public int climbStairs(int n) {
        return fastPower(n - 1);
    }
    
    int[][] mul(int[][] a, int[][] b) {
        int[][] res = new int[2][2];
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                res[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j];
            }
        }
        return res;
    }
    
    int fastPower(int n) {
        int[][] x = new int[][]{{1, 1}, {1, 0}};
        int[][] res = x;
        while (n > 0) {
            if ((n & 1) == 1) {
                res = mul2(res, x);
            }
            x = mul(x, x);
            n >>= 1;
        }
        return res[0][0];
    }
}
